package org.hot100.h142;

import java.util.*;

/**
 * @Author: wjy
 * @Date: 2021/12/31 9:35
 */
public class Solution {

    public static void main(String[] args) {

        ListNode listNode1 = new ListNode(-4);
        ListNode listNode2 = new ListNode(0);
        ListNode listNode3 = new ListNode(2);
        ListNode listNode4 = new ListNode(3);

        listNode4.next = listNode3;
        listNode3.next = listNode2;
        listNode2.next = listNode1;
        listNode1.next = listNode3;

        Solution solution = new Solution();
        System.out.println(solution.detectCycle4(listNode4).val);
        
    }

    /**
     * 执行用时：309 ms, 在所有 Java 提交中击败了12.42%的用户
     * 内存消耗：38.7 MB, 在所有 Java 提交中击败了20.10%的用户
     *
     * @param head
     * @return
     */
    public ListNode detectCycle2(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;
        List<ListNode> listNodes = new ArrayList<>();
        listNodes.add(fast);

        while (true) {
            slow = slow.next;
            fast = fast.next;
            if (fast != null) {
                if (listNodes.contains(fast)) {
                    return fast;
                }
                listNodes.add(fast);
                fast = fast.next;
                if (fast != null) {
                    if (listNodes.contains(fast)) {
                        return fast;
                    }
                    listNodes.add(fast);
                }
            }
            if (slow == null || fast == null) {
                return null;
            }
            if (slow == fast) {
                return fast;
            }
        }

    }

    /**
     * 绝！！！
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：38.7 MB, 在所有 Java 提交中击败了20.52%的用户
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;

        // 首先找出相遇位置
        while (true) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }

        // 将fast指向头节点，相遇时fast走的次数两倍于slow，所以当fast从头开始和slow以相同速度走，他们一定会在第一个相交节点相遇！！！
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }

    public ListNode detectCycle3(ListNode head) {

        ListNode slow = head;
        ListNode fast = head;

        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }

        fast = head;
        while (true) {
            fast = fast.next;
            slow = slow.next;
            if (slow == fast) {
                return slow;
            }

        }
    }

    public ListNode detectCycle4(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            if (slow == fast) {
                break;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        slow = head;
        while (true) {
            slow = slow.next;
            fast = fast.next;
            if (slow == fast) {
                return slow;
            }
        }
    }

}
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}